/*
 * 拓扑分析算法库
 */
define(["require", "exports","./LinearAlgebra"], function (require, exports, LinearAlgebra) {
    function Topology() {
         this.linearAlgebra = new LinearAlgebra();
    }

   
    
    //点集聚合分析(中心聚合) points:[[x1,y1],[x2,y2],...]
    Topology.prototype.PointsCluster = function(points,MaxDis){
    	//聚合要素对象 {id:0, centerPoint:[x1,y1], items:[{id:0,point:[x2,y2]}],type:"group"}
    	 //孤立要素对象 {id:0,point:[x,y],type:"alone"}
    	
    	//聚合组对象
    	var clusterItems = []; 
    	
    	//将所有点要素封装到孤立要素中
    	for(var i = 0; i< points.length;i++){
           var clusterItem = {id:i, point:points[i], type:"alone"};
           clusterItems.push(clusterItem);
        }
        
        //循环遍历聚合组中的要素
        for(var i=0;i<clusterItems.length;i++){
            var item = clusterItems[i];
            var geom = null;
            //该要素为孤立要素
            if(item.type == "alone"){
                geom = item.point;
            }
            //该要素要素为聚合要素
            else if(item.type == "group"){
                geom = item.centerPoint;
            }
            //与其他要素进行相邻关系判定
            for(var j=0;j<clusterItems.length;j++){
            	//如果两个要素为都为聚合要素则不作聚合
                if(j==i || (clusterItems[j].type=="group" && item.type=="group")) 
                    continue;
                var item2 = clusterItems[j];
                var type2 = item2.type;
                var geom2 = null;
                if(type2 == "alone"){
                    geom2 = item2.point;
                }
                else if(type2 == "group"){
                    geom2 = item2.centerPoint;
                }
                var dis = Math.sqrt(Math.pow(geom[0]-geom2[0],2)+Math.pow(geom[1]-geom2[1],2));
                if(dis>MaxDis)
                    continue;
              if(item.type == "alone" && item2.type == "group")
                { 
                	var point = {id:item.id,point:item.point};
                	item2.items.push(point);
                	
                    var x = (geom[0]+geom2[0])/2;
                    var y = (geom[1]+geom2[1])/2;
                    item2.centerPoint=[x,y];
                    //将后一个聚合要素替换前一个孤立要素
                    clusterItems[i]=item2;
                    clusterItems.splice(j,1);
                    //重新开始遍历
                    i--;
                    j=0;
                }
                else if(item.type == "group" && item2.type == "alone"){
                	var point = {id:item2.id,point:item2.point}; 
                	item.items.push(point);
                	
                	var x = (geom[0]+geom2[0])/2;
                    var y = (geom[1]+geom2[1])/2;
                    item.centerPoint = [x,y];
                    //删除后一个孤立要素
                    clusterItems.splice(j,1);
                    //重新开始遍历
                    i--;
                    j=0;
                }
                else if(item.type=="alone" && item2.type =="alone"){
                	var group = {id:item.id, items:[], centerPoint:[], type:"group"};
                	var point1 = {id:item.id,point:item.point};
                	var point2 = {id:item2.id,point:item2.point};
                	group.items=[point1,point2];
                	var x = (geom[0]+geom2[0])/2;
                    var y = (geom[1]+geom2[1])/2;
                	group.centerPoint = [x,y];
                	//替换前一个孤立元素
                	clusterItems[i] = group;
                	//删除后一个孤立元素
                	clusterItems.splice(j,1);
                	//重新开始遍历
                    i--;
                    j=0;
                }
            }
        }
    }
    
    /*
     * 点集分区算法
     * points:表示点集 数据结构：[[x1,y1],[x2,y2],、、]
     * distance:表示缓冲距离
     */
    Topology.prototype.PointsPartition = function(points,distance){
    	
    }
    
     /*
      * 点集求外包凸多边形
      * inPoints:输入的点集 结构：[[x1,y1],[x2,y2],、、、]
      * 返回值结构 [{"index":0,"coordinate":[x1,y1]},{"index":1,"coordinate":[x2,y2]},、、、、]
      */
    Topology.prototype.OutConvexPolgon = function(inPoints){
    	var point_list =[];
    	var basePoint = {};//参考点
    	var baseVector = [];//参考向量
    	var polygon_pointlist = [];//外凸多边形点集
    	//封装用于分析的点集
    	for(var i=0;i<inPoints.length;i++){
    		var pointObj = {"index":i,"coordinate":[0,0]};
            pointObj.coordinate = inPoints[i];
            point_list.push(pointObj);
            //初始化参考点，将其设置为点集中最左边的点
            if(i==0)
              basePoint = pointObj;
            else{
            	if(basePoint.coordinate[0]>pointObj.coordinate[0])
            	  basePoint = pointObj;
            }
    	}
    	//初始化参考向量，垂直向上
    	baseVector = [0,10];
    	polygon_pointlist.push(basePoint);
    	
    	//开始分析
    	for(var i = 0; i< point_list.length;i++)
    	{
    		var nextPoint = null;
    		var minAngle = Infinity;
    		//寻找下一个多边形节点
    		for(var j = 0; j< point_list.length;j++)
    		{
    			var newPoint = point_list[j];
    		    if(newPoint.index == basePoint.index)
    		        continue;
    		    var newVector = [newPoint.coordinate[0]-basePoint.coordinate[0],newPoint.coordinate[1]-basePoint.coordinate[1]];
    		    var angle = this.linearAlgebra.GetVectorsRotateAngle(baseVector,newVector);
    		    if(j==0)
    		    {
    		    	minAngle = angle;
    		    	nextPoint = newPoint;
    		    }
    		    else{
    		    	if(angle<minAngle){
    		    		minAngle = angle;
    		    		nextPoint = newPoint;
    		    	}
    		    }
    		}
    		
    		var isClose = polygon_pointlist.filter(function(item){return item.index==nextPoint.index}).length;
    		//判断外凸变形的点集是否闭合
    		if(isClose)
    		{
    			break;
    		}
    		baseVector = [nextPoint.coordinate[0]-basePoint.coordinate[0],nextPoint.coordinate[1]-basePoint.coordinate[1]];
    		basePoint = nextPoint;
    		polygon_pointlist.push(nextPoint);
    	}
    	return polygon_pointlist;
    }
    
    
  
    /*
     * 求点与多边形的拓扑关系
     * polygon: 表示构成多边形的点集 数据结构[[x1,y1],[x2,y2],、、、]
     * point：判断关系的点 数据结构[x1,y1]
     * 返回值： "in":重合，"edge":边缘重合，"out:"不重合
     */
    Topology.prototype.PolygonPointRel = function(polygon,point){
    	var count = 0; //点往左的射线与多边形边的相交点的数量
    	var y = point[1];
    	for(var i =0 ;i<polygon.length;i++){
    		var point1 = polygon[i];
    		var j=i+1;
    		if(j==polygon.length)
    		j=0;
    		var point2 = polygon[j];
    		
    		//如果点与多边形节点重合
    		if((point1[0]==point[0])&&(point1[1]==point[1]))
    		{
    			return "edge";
    		}
    		if((point2[0]==point[0])&&(point2[1]==point[1]))
    		{
    			return "edge";
    		}
    		
    		//如果边线与y轴平行
    		if(point1[0]==point2[0])
    		{
    			var limit_y = [];
    			if(point1[1]<=point2[1])
    			    limit_y=[point1[1],point2[1]];
    			else
    			    limit_y=[point2[1],point1[1]];
    			
    			if(y<limit_y[0]||y>limit_y[1]){
    				continue;
    			}
    			//如果点与连线重合，直接返回值"edge"
    			if(point1[0]==point[0]){
    				return "edge";
    			}
    			//判断连线是否在点的左边
    			if(point[0]<point1[0]){
    				continue;
    			}
    		    count++;
    			continue;
    		}
    		
    		//如果边线与x轴平行
    		if(point1[1]==point2[1])
    		{
    			//判断射线是否与与连线到x轴的距离相同
    			if(point1[1]!=point[1])
    			    continue;
    			var limit_x=[];
    			if(point1[0]>point2[0])
    			    limit_x = [point2[0],point1[0]];
    			else
    				limit_x = [point1[0],point2[0]];
    			
    			if(x<=limit_x[1]&&x>=limit_x[0])
    			    return "edge";
    			else
    			    return "out";
    		}
    		
    		var k = (point2[1]-point1[1])/(point2[0]-point1[0]);
    		var b = point1[1]-(k*point1[0]);
    		var limit_x = [];
    		if(point1[0]<=point2[0])
    		    limit_x=[point1[0],point2[0]];
    		else
    		    limit_x=[point2[0],point1[0]];
    		var x = (y-b)/k;
    		if(x>limit_x[0]&&x<limit_x[1]&&x<point[0])
    		    count++;
    		//如果点就在边线上,直接返回结果
    		if(x==point[0]){
    			return "edge";
    		}
    		//如果点的左射线与边线上的前一个节点相交
    		if(x==point1[0]&&x<point[0])
    		{
    			var index = (i-1==-1?polygon.length-1:i-1);
    			var pointlast = polygon[index];
    			var pointnext = point2;
    			var dylast = pointlast[1] - point1[1];
    			var dynext = pointnext[1] - point1[1];
    			if(dylast*dynext<0)
    			    count++;
    			continue;
    		}
    	}
    	var result = "";
    	//相交点数量为偶数
    	if(count%2==0)
    	result = "out";
    	//相交点数量为基数
    	else
    	result = "in";
    	return result;
    }


    /*
     * 求三角形外接圆
     * triangle: 表示参与分析的多边形，数据结构[[x1,y1],[x2,y2],[x3,y3]]
     */
    Topology.prototype.TriangleGetCircumcircle = function(tri){
    	var edge_k =  (tri[1][1]-tri[0][1])/(tri[1][0]-tri[0][0]);
    	var edgePoint = [(tri[0][0]+tri[1][0])/2,(tri[0][1]+tri[1][1])/2];
    	var line1 = [edgePoint];
    	if(edge_k == Infinity){
    		line1.push([edgePoint[0]+1,edgePoint[1]]);
    	}
    	else if(edge_k==0){
    		line1.push([edgePoint[0],edgePoint[1]+1]);
    	}
    	else{
    		var k = -1/edge_k;
    	    b = edgePoint[1]-k*edgePoint[0];
    	    line1.push([edgePoint[0]+1,k*(edgePoint[0]+1)+b]);
    	}
    	
    	edge_k =  (tri[2][1]-tri[1][1])/(tri[2][0]-tri[1][0]);
    	edgePoint = [(tri[2][0]+tri[1][0])/2,(tri[2][1]+tri[1][1])/2];
    	var line2 = [edgePoint];
    	if(edge_k == Infinity){
    		line2.push([edgePoint[0]+1,edgePoint[1]]);
    	}
    	else if(edge_k==0){
    		line2.push([edgePoint[0],edgePoint[1]+1]);
    	}
    	else{
    		var k = -1/edge_k;
    	    b = edgePoint[1]-k*edgePoint[0];
    	    line2.push([edgePoint[0]+1,k*(edgePoint[0]+1)+b]);
    	}
    	//上面已获取两个中垂线
    	//下面获取两条中垂线的交点
       var rel = this.linearAlgebra.LineLineRel(line1,line2,false,false);
       //获取圆的坐标半径
       var point = rel.coordinate;
       var radius = Math.sqrt(Math.pow(tri[0][0]-point[0],2)+Math.pow(tri[0][1]-point[1],2));
       return {"coordinate":point,"radius":radius}
    }


      return Topology;
});
